package com.graph.impl;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

import com.graph.base.Edge;
import com.graph.base.GraphBase;
import com.graph.base.GraphInterface;
import com.graph.base.VertexInterface;
import com.graph.similar.ConsineSimilar;
import com.graph.util.GraphFileUtils;

/**
 * @author LiWu
 */
public class DensityCenterGraph extends GraphBase implements GraphInterface{

	private double numCommunity;
    double totalDensity = 0;
    double averageDensity = 0;//0.12 0.16 0.09

	public void setAverageDensity(double averageDensity) {
		this.averageDensity = averageDensity;
	}

	public double getAverageDensity() {
		return averageDensity;
	}

	private Map<Set<String>,Set<VertexInterface>> localMinCommunity = new LinkedHashMap<Set<String>, Set<VertexInterface>>();
	
	private List<VertexInterface> restIndependentVertexs = new ArrayList<VertexInterface>();

	private List<VertexInterface> vertexList = new ArrayList<VertexInterface>();

	private ConsineSimilar consineSimilar = new ConsineSimilar();

    public DensityCenterGraph(String dataPath, String fileName, int numCommunity) {
    	this.numCommunity = numCommunity;
    	GraphFileUtils.getInstance().read(dataPath, fileName, this);
		init();
	}

	/**
	 * init the network
     */
    private void init(){
    	List<VertexInterface> allvers = getVerticesList();
		vertexList = allvers;
		System.out.println("Density:");
    	for (VertexInterface vertexInterface : allvers) {
    		double density = getDensity(getlocalGraphByVertexs(vertexInterface, 3));
			System.out.println(vertexInterface.getName() + " : " + density);
    		totalDensity += density;
			vertexInterface.setDensity(density);
		}
		System.out.println();
		Collections.sort(allvers, new Comparator<VertexInterface>(){
    		@Override
    		public int compare(VertexInterface o1, VertexInterface o2) {
    			double q1 = o1.getDensity();
    			double q2 = o2.getDensity();
    			if(q1 == q2){
            		return 0;
            	}else if(q1 > q2){
            		return -1;
            	}else{
            		return 1;
            	}
    		}
    	});
		Map<String, VertexInterface> map = getVertices();
		setAverageDensity(allvers.get((int)(Math.ceil(map.size()/2))).getDensity());
    }

    private double getDiffDensity(List<VertexInterface> allers){
    	double cha = 10;
    	double resultDensity = 0;
    	VertexInterface lastVer = null;
    	for (int i = 0; i < allers.size() / 2; i++) {
    		VertexInterface vertexInterface = allers.get(i);
    		if(lastVer != null){
				double nowCha = lastVer.getDensity() - vertexInterface.getDensity();
				if(nowCha < cha){
					cha = nowCha;
					resultDensity = lastVer.getDensity();
				}
			}
			lastVer = vertexInterface;
		}
		return resultDensity;
    }
    
    private double figureQ(Map<Set<String>, Set<VertexInterface>> obj, Boolean isFull){
    	Map<VertexInterface, Integer> vertexInterfaceIntegerMap = new LinkedHashMap<VertexInterface, Integer>();
    	Iterator<Set<String>> it = obj.keySet().iterator();
		int num = 0;
    	while(it.hasNext()){
    		num ++;
			Set<String> key = it.next();
			Set<VertexInterface> community = obj.get(key);
			Iterator<VertexInterface> it2 = community.iterator();
			while(it2.hasNext()){
				vertexInterfaceIntegerMap.put(it2.next(), num);
			}
		}
    	double nowQ = 0;
    	if(!isFull){
    		nowQ = modularityQ1(vertexInterfaceIntegerMap);
    	}else{
    		nowQ = modularityQ(vertexInterfaceIntegerMap);
    	}
		System.out.println("Q: " + nowQ);
		return nowQ;
    }

	public double modularityQ1(Map<VertexInterface, Integer> vertexInterfaceMap){
		List<VertexInterface> allvers = getVerticesList();
		Integer verNum = allvers.size();
		double q = 0.0;
		int m2 = getEdge(new ArrayList<VertexInterface>(vertexInterfaceMap.keySet())).size();
		for (int i = 0; i < verNum; i++) {
			for (int j = 0; j < verNum; j++) {
				if(i != j){
					VertexInterface v1 = allvers.get(i);
					VertexInterface v2 = allvers.get(j);
					Integer t1 = vertexInterfaceMap.get(v1);
					Integer t2 = vertexInterfaceMap.get(v2);
					if(t1 == null || t2 == null) {
						continue;
					}
					if(vertexInterfaceMap.get(v1).equals(vertexInterfaceMap.get(v2))){
						double de = v1.getDegree() * v2.getDegree();
						double l = de / m2;
						if(isNeighbor(v1, v2)){
							q = q + 1 - l;
						}else{
							q = q - l;
						}
					}
				}
			}
		}
		return q / m2;
	}

	@Override
	public double modularityQ(Map<VertexInterface, Integer> vertexInterfaceMap){
		List<VertexInterface> allvers = getVerticesList();
		Integer verNum = allvers.size();
		double q = 0.0;
		int m2 = getNumberOfEdges();
		for (int i = 0; i < verNum; i++) {
			for (int j = 0; j < verNum; j++) {
				if(i != j){
					VertexInterface v1 = allvers.get(i);
					VertexInterface v2 = allvers.get(j);
					Integer t1 = vertexInterfaceMap.get(v1);
					Integer t2 = vertexInterfaceMap.get(v2);
					if(t1 == null || t2 == null) {
						continue;
					}
					if(vertexInterfaceMap.get(v1).equals(vertexInterfaceMap.get(v2))){
						double de = v1.getDegree() * v2.getDegree();
						double l = de / m2;
						if(isNeighbor(v1, v2)){
							q = q + 1 - l;
						}else{
							q = q - l;
						}
					}
				}
			}
		}
		return q / m2;
	}

    private void mergeCommunity(){
    	double q1 = figureQ(localMinCommunity, true);
		Iterator<Set<String>> it = localMinCommunity.keySet().iterator();
		while(it.hasNext()){
			Set<String> stringSet = it.next();
			Set<VertexInterface> unitCommunities = localMinCommunity.get(stringSet);
			double r1 = modularityR(unitCommunities);
			Set<Set<String>> nearCommunity = new HashSet<Set<String>>();
			for(VertexInterface vertexInterface : unitCommunities) {
				nearCommunity.addAll(getNearCommunityByVertex(vertexInterface));
			}
			Iterator<Set<String>> it1 = nearCommunity.iterator();
			double r3 = 0;
			Set<String> stringSet1 = null;
			while(it1.hasNext()){
				Set<String> stringSet2 = it1.next();
				if(stringSet == stringSet2) {
					continue;
				}
				Set<VertexInterface> nearCommunity1 = localMinCommunity.get(stringSet2);
				double r2 = modularityR(nearCommunity1);
				Set<VertexInterface> newCommunity = new HashSet<VertexInterface>();
				newCommunity.addAll(unitCommunities);
				newCommunity.addAll(nearCommunity1);
				double tR = modularityR(newCommunity);
				if(tR >= r2 || tR >= r1){
					r3 = tR;
					stringSet1 = stringSet2;
				}
			}
			if(r3 != 0){
				Map<Set<String>, Set<VertexInterface>> obj = new LinkedHashMap<Set<String>, Set<VertexInterface>>(localMinCommunity);
				Set<VertexInterface> newLocalMinCommunity = new HashSet<VertexInterface>();
				newLocalMinCommunity.addAll(unitCommunities);
				newLocalMinCommunity.addAll(obj.get(stringSet1));
				Set<String> stringSet3 = new HashSet<String>();
				obj.remove(stringSet);
				obj.remove(stringSet1);
				stringSet3.addAll(stringSet1);
				stringSet3.addAll(stringSet);
				obj.put(stringSet3, newLocalMinCommunity);
				double qt = figureQ(obj, true);
				if(qt >= q1){
					localMinCommunity = obj;
					mergeCommunity();
					return;
				}
			}
		}
		return ;
    }
    
    private Set<Set<String>> getNearCommunityByVertex(VertexInterface ver){
    	Set<VertexInterface> negs = getNeighbors(ver);
		Set<Set<String>> nearbyCommunity = new HashSet<Set<String>>();
		for (VertexInterface vertexInterface : negs) {
			Set<String> names = getSelfCommunityByVertex(vertexInterface);
			if(names != null){
				nearbyCommunity.add(names);
			}
		}
		return nearbyCommunity;
    }

    private void combineSingleVertes(){
    	List<VertexInterface> needRemoveIndependVertex = new ArrayList<VertexInterface>();
    	Collections.sort(restIndependentVertexs, new Comparator<VertexInterface>(){
    		@Override
    		public int compare(VertexInterface o1, VertexInterface o2) {
    			double q1 = o1.getDensity();
    			double q2 = o2.getDensity();
    			if(q1 == q2){
            		return 0;
            	} else if(q1 > q2){
            		return -1;
            	}else{
            		return 1;
            	}
    		}
    	});
    	for (VertexInterface vertexInterface : restIndependentVertexs) {
    		Set<Set<String>> nearCommunity = getNearCommunityByVertex(vertexInterface);
    		if(combineVertes2(nearCommunity, vertexInterface)){
    			needRemoveIndependVertex.add(vertexInterface);
    		}
		}
    	restIndependentVertexs.removeAll(needRemoveIndependVertex);
    }

	private boolean combineVertes(Set<Set<String>> nearbyCommunity, VertexInterface vertexInterface){
		Set<String> mayBaNameKeys = null;
		Set<VertexInterface> mayNewCommunity = new HashSet<VertexInterface>();
		for(Set<String> keyName : nearbyCommunity) {
			Set<VertexInterface> old = localMinCommunity.get(keyName);
			double r = modularityR(old);
			Set<VertexInterface> newCommunity = new HashSet<VertexInterface>(old);
			newCommunity.add(vertexInterface);
			double r1 = modularityR(newCommunity);
			//??R????
			if(r1 - r > 0){
				if(mayBaNameKeys == null){
					mayBaNameKeys = keyName;
					mayNewCommunity.addAll(newCommunity);
				}else{
					mayBaNameKeys = null;
					mayNewCommunity.clear();
					break;
				}
			}
		}
		if(mayBaNameKeys != null && mayBaNameKeys.size() != 0){
			List<String> newkeyName = new ArrayList<String>(mayBaNameKeys);
			newkeyName.add(vertexInterface.getName());
			localMinCommunity.remove(mayBaNameKeys);
			localMinCommunity.put(new HashSet<String>(newkeyName), mayNewCommunity);
			return true;
		}
		return false;
	}

	private boolean combineVertes2(Set<Set<String>> nearbyCommunity, VertexInterface vertexInterface){
		Map<Set<String>, Set<VertexInterface>> mayBeNameKeysNeed = new HashMap<Set<String>, Set<VertexInterface>>(16);
		Set<String> mayBeNameKeys = null;
		Set<VertexInterface> mayNewCommunity = new HashSet<VertexInterface>();
		for(Set<String> keyName : nearbyCommunity) {
			Set<VertexInterface> old = localMinCommunity.get(keyName);
			double r = modularityR(old);
			Set<VertexInterface> newCommunity = new HashSet<VertexInterface>(old);
			if(newCommunity.contains(vertexInterface)){
				return true;
			}
			newCommunity.add(vertexInterface);
			double r1 = modularityR(newCommunity);
			if(r1 - r > 0){
				if(mayBeNameKeys == null){
					mayBeNameKeys = keyName;
					mayNewCommunity.addAll(newCommunity);
					mayBeNameKeysNeed.put(keyName, old);
				}else{
					mayBeNameKeysNeed.put(keyName, old);
				}
			}
		}
		if(mayBeNameKeysNeed.size() == 1){
			if(mayBeNameKeys != null){
				List<String> newkeyName = new ArrayList<String>(mayBeNameKeys);
				newkeyName.add(vertexInterface.getName());
				localMinCommunity.remove(mayBeNameKeys);
				localMinCommunity.put(new HashSet<String>(newkeyName), mayNewCommunity);
				return true;
			}
		}else if(mayBeNameKeysNeed.size() > 1){
    		int maxEdges = 0;
    		Set<String> maxKeyName = null;
    		Set<VertexInterface> neighbors = getNeighbors(vertexInterface);
    		for(Set<String> keyName : mayBeNameKeysNeed.keySet()) {
    			int numEd = 0;
    			for(VertexInterface v : neighbors){
    				if(keyName.contains(v.getName())){
    					numEd ++;
    				}
    			}
    			if(numEd > maxEdges){
    				maxKeyName = keyName;
    				maxEdges = numEd;
    			}else if(numEd == maxEdges){
    			}
    		}
    		if(maxKeyName != null){
    			Set<String> newKey = new HashSet<String>(maxKeyName);
    			newKey.add(vertexInterface.getName());
    			Set<VertexInterface> newValue = new HashSet<VertexInterface>(localMinCommunity.get(maxKeyName));
    			newValue.add(vertexInterface);
    			localMinCommunity.put(newKey, newValue);
    			localMinCommunity.remove(maxKeyName);
    			return true;
    		}
		}
		return false;
	}

	/**
	 * init community
     */
	private void createlocalMinCommunity(){
		List<VertexInterface> allvers = getVerticesList();
		List<VertexInterface> havaSlect = new ArrayList<VertexInterface>();
		for (VertexInterface vertexInterface : allvers) {
			if(vertexInterface.getDensity() <= getAverageDensity()){
				if(!havaSlect.contains(vertexInterface)){
					restIndependentVertexs.add(vertexInterface);
				}
				continue;
			}
			Set<VertexInterface> neighbors = getNeighbors(vertexInterface);
			Set<String> keys = new HashSet<String>();
			HashSet<VertexInterface> minCommunity = new HashSet<VertexInterface>();
			double min = 0;
			for (VertexInterface vertexInterface1 : neighbors) {
				double d2 = vertexInterface1.getDensity();
				if(d2 > min){
					min = d2;
					minCommunity.clear();
					minCommunity.add(vertexInterface1);
				}else if(d2 == min){
					minCommunity.add(vertexInterface1);
				}
			}
			Iterator<VertexInterface> vertexInterfaceIterator = minCommunity.iterator();
			while(vertexInterfaceIterator.hasNext()){
				VertexInterface ver = vertexInterfaceIterator.next();
				restIndependentVertexs.remove(ver);
				ver.visit();
				keys.add(ver.getName());
				havaSlect.add(ver);
			}
			keys.add(vertexInterface.getName());
			minCommunity.add(vertexInterface);
			localMinCommunity.put(keys,minCommunity);
		}
	}

    private void filter2PointCommunnity() {
    	List<VertexInterface> vertexInterfaceList = new ArrayList<VertexInterface>();
    	List<Set<String>> returnKeys = new ArrayList<Set<String>>();
    	Iterator<Set<String>> it = localMinCommunity.keySet().iterator();
		while(it.hasNext()){
			Set<String> key = it.next();
			if(key.size() <= 2){
				returnKeys.add(key);
			}
		}
		for(Set<String> list : returnKeys) {
			vertexInterfaceList.addAll(localMinCommunity.get(list));
			localMinCommunity.remove(list);
		}
		restIndependentVertexs.addAll(vertexInterfaceList);
	}

	private Set<String> getSelfCommunityByVertex(VertexInterface vertexInterface){
    	String name = vertexInterface.getName();
    	Set<Set<String>> keys = localMinCommunity.keySet();
    	Iterator<Set<String>> it = keys.iterator();
    	while(it.hasNext()){
    		Set<String> stringSet = it.next();
    		if(stringSet.contains(name)){
    			return stringSet;
    		}
    	}
    	return null;
    }

    private double getDensity(List<VertexInterface> g){
    	double e = getEdge(g).size() / 2;
    	if(e == 0){
    		return 0;
    	}
    	double v = g.size();
    	return e / (v * (v - 1) / 2);
    }

    private List<VertexInterface> getlocalGraphByVertexs(VertexInterface ver,Integer level){
    	resetVertices();
    	List<VertexInterface> result = new ArrayList<VertexInterface>();
    	result.add(ver);
		Queue<VertexInterface> vertexQueue = new LinkedList<>();
		ver.visit();
		vertexQueue.offer(ver);
		while (!vertexQueue.isEmpty()) {
			VertexInterface frontVertex = vertexQueue.poll();
			Iterator<VertexInterface> neighbors = frontVertex.getNeighborInterator();
			while (neighbors.hasNext()) {
				VertexInterface nextNeighbor = neighbors.next();
					if(!nextNeighbor.isVisited()){
						nextNeighbor.visit();
						nextNeighbor.setCost(frontVertex.getCost() + 1);
						result.add(nextNeighbor);
						if(nextNeighbor.getCost() < level){
							vertexQueue.offer(nextNeighbor);
					    }
					}
				}
			}
    	resetVertices();
		return result;
    }

	@Override
	public Set<VertexInterface> findCommunityByVertices(String ver)
			throws Exception {
		// TODO Auto-generated method stub
		return null;
	}

	public List<Set<VertexInterface>> findAllCommunity1() throws Exception {
		List<Set<VertexInterface>> result = new ArrayList<Set<VertexInterface>>();
	   	createlocalMinCommunity();
	   	mergeCommunityInit();
	   	combineSingleVertes();
	   	double q = 0;
	   	double q1 = 0;
	   	do{
			do{
				q = q1;
				mergeCommunity();
				combineSingleVertes();
				q1 = figureQ(localMinCommunity, true);
			}while(q1 > q);
			if(restIndependentVertexs.size() != 0) {
				forceCombineSingleVertes();
				mergeCommunity();
			}
			removeRepeatVertics();
	   	}while(restIndependentVertexs.size() != 0);
	   	Iterator<Set<VertexInterface>> it = localMinCommunity.values().iterator();
	   	while(it.hasNext()){
	   		result.add(it.next());
	   	}
	   	initNowAnswer(result);
	   	return result;
	}

	/**
	 * community detection
	 * @return
	 * @throws Exception
     */
	@Override
	public List<Set<VertexInterface>> findAllCommunity() throws Exception {
		List<Set<VertexInterface>> result = new ArrayList<Set<VertexInterface>>();
		createlocalMinCommunity();
		mergeFuzzyCommunity();//merge community by fuzzy math
		do{
			System.out.println("The number of independent vertex is " + restIndependentVertexs.size());
			mergeFuzzyVertexByRfunction();//merge fuzzy vertex by R function
		}while (restIndependentVertexs.size() != 0);
//		combineFuzzyVertes();
		Iterator<Set<VertexInterface>> it = localMinCommunity.values().iterator();
		while(it.hasNext()){
			result.add(it.next());
		}
		initNowAnswer(result);
		return result;
	}

	private void mergeFuzzyCommunity() {
//		int size = localMinCommunity.size() + restIndependentVertexs.size();
		int size = localMinCommunity.size();
		System.out.println("The number of init community is " + size);
		double[][] fuzzySimilarMatrix = new double[size][size];
		double[][] fuzzySimilarMatrix1 = new double[size][size];
		double[][] fuzzyEquivalenceMatrix = new double[size][size];
		List<Set<VertexInterface>> vertexInterfaceList = new ArrayList<Set<VertexInterface>>();
		Map<Integer, Set<String>> communityMap = new HashMap<Integer, Set<String>>(16);
		int num = 1;
		for(Set<String> keyName : localMinCommunity.keySet()){
			vertexInterfaceList.add(localMinCommunity.get(keyName));
			communityMap.put(num, keyName);
			num ++;
		}
//		int sum = communityMap.size() + 1;
//		for(VertexInterface vertexInterface : restIndependentVertexs){
//			Set<VertexInterface> vertexInterfaceSet = new HashSet<VertexInterface>();
//			vertexInterfaceSet.add(vertexInterface);
//			//???????????????
//			vertexInterfaceList.add(vertexInterfaceSet);
//			Set<String> stringSet = new HashSet<String>();
//			stringSet.add(vertexInterface.getName());
//			communityMap.put(sum, stringSet);
//			sum++;
//		}
		for(int i = 0; i < size; i ++){
			for(int j = 0; j < size; j ++){
				double similar = getSimilar(vertexInterfaceList.get(i), vertexInterfaceList.get(j));
				BigDecimal bigDecimal = new BigDecimal(similar);
				similar = bigDecimal.setScale(3, RoundingMode.UP).doubleValue();
				fuzzySimilarMatrix[i][j] = similar;
			}
		}
		fuzzySimilarMatrix1 = fuzzySimilarMatrix;
		System.out.println("Similar matrix: ");
		for(int i = 0; i < size; i ++){
			for(int j = 0; j < size; j ++){
				System.out.printf("%1.3f", fuzzySimilarMatrix[i][j]);
				System.out.print("  ");
			}
			System.out.println();
		}
		System.out.println();
		int n = 1;
		do{
			fuzzyEquivalenceMatrix = getEquivalenceMatrix(fuzzySimilarMatrix, fuzzySimilarMatrix1);
			fuzzySimilarMatrix = fuzzyEquivalenceMatrix;
			n ++;
		}while (n <= size);
		System.out.println("Equivalence matrix: ");
		double totalSimilar = 0;
		for(int i = 0; i < size; i ++){
			for(int j = 0; j < size; j ++){
				totalSimilar += fuzzyEquivalenceMatrix[i][j];
				System.out.printf("%1.3f", fuzzyEquivalenceMatrix[i][j]);
				System.out.print("  ");
			}
			System.out.println();
		}
		if(size > 1){
			BigDecimal bigDecimal = new BigDecimal(totalSimilar / (size * size));
			BigDecimal bigDecimal1 = new BigDecimal(averageDensity);
			System.out.println("Average similar: " + bigDecimal.setScale(3, RoundingMode.UP).doubleValue());
			System.out.println("Average density: " + bigDecimal1.setScale(3, RoundingMode.UP).doubleValue());
			System.out.println();
		}
		//classify community
		Map<Integer, List<String>> communityClass = communityClassifiy(fuzzyEquivalenceMatrix);
		//again init unit community
		localMinCommunity = new HashMap<Set<String>, Set<VertexInterface>>(16);
		for(Integer integer : communityClass.keySet()){
			List<String> stringList = communityClass.get(integer);
			System.out.println(stringList);
		}
		System.out.println();
//		for(Integer integer : communityClass.keySet()){
			List<String> stringList = communityClass.get(3);
			System.out.println(stringList);
			System.out.println("The number of community is " + stringList.size());
			for(String str : stringList){
				Set<String> keyName = new HashSet<>();
				Set<VertexInterface> vertexInterfaceSet = new HashSet<VertexInterface>();
				List<String> vertexInterfaceList1 = new ArrayList<String>();
				String[] arr = str.split("_");
				for(String s : arr){
					Set<String> vertexInterfaces = communityMap.get(Integer.valueOf(s));
					for(String string : vertexInterfaces){
						if(!vertexInterfaceList1.contains(string)){
							vertexInterfaceList1.add(string);
						}
					}
				}
				for(String vertexName : vertexInterfaceList1){
					keyName.add(vertexName);
					System.out.print(vertexName+" ");
					for(VertexInterface vertexInterface : vertexList){
						if(vertexName.equals(vertexInterface.getName())){
							vertexInterfaceSet.add(vertexInterface);
						}
					}
				}
				System.out.println();
				localMinCommunity.put(keyName, vertexInterfaceSet);
			}
			System.out.println();
//		}
	}

	/**
	 * ??lambda??????
	 * @param matrix
     */
	private Map<Integer, List<String>> communityClassifiy(double[][] matrix){
		Map<Integer, List<String>> communityClass = new HashMap<Integer, List<String>>(16);
		int size = matrix.length;
		int[][] matrix1 = new int[size][size];
		int lambda = 5;
		int num = 1;
		do{
			for(int i = 0; i < size; i ++){
				for(int j = 0; j < size; j ++){
					if(matrix[i][j] >= lambda/(double)100){
						matrix1[i][j] = 1;
					}else{
						matrix1[i][j] = 0;
					}
				}
			}
			List<String> conmmunityClass = classify(matrix1);
			communityClass.put(num, conmmunityClass);
			num ++;
			lambda += 5;
		}while (lambda <= 100);
		return communityClass;
	}

	/**
	 * classify community by different lambda
	 * @param matrix
     */
	private List<String> classify(int[][] matrix){
		List<String> communityClass = new ArrayList<String>();
		Set<String> vertexSet = new HashSet<String>();
		int size = matrix.length;
		for(int i = 0; i < size; i ++){
			for(int j = 0; j < size; j ++){
				if(i < j){
					String row = String.valueOf(i + 1);
					String column = String.valueOf(j + 1);
					String str = row + "_" + column;
					if(matrix[i][j] == 1){
						communityClass.add(str);
					}else {
						vertexSet.add(row);
						vertexSet.add(column);
					}
				}
			}
		}
		for(int i = 0 ; i < communityClass.size(); i++){
			for(int j = i + 1; j < communityClass.size(); j++){
				String string = communityClass.get(i);
				String[] arr1 = string.split("_");
				String[] arr2 = communityClass.get(j).split("_");
				if(Arrays.asList(arr1).contains(arr2[0])){
					if(!Arrays.asList(arr1).contains(arr2[1])){
						string = string + "_" + arr2[1];
					}
					communityClass.remove(j);
					j--;
				}else if(Arrays.asList(arr1).contains(arr2[1])){
					if(!Arrays.asList(arr1).contains(arr2[0])){
						string = string + "_" + arr2[0];
					}
					communityClass.remove(j);
					j--;
				}
				if(!communityClass.contains(string)){
					communityClass.add(i, string);
				}
			}
		}
		for(int i = 0 ; i < communityClass.size(); i++) {
			for (int j = i + 1; j < communityClass.size(); j++) {
				if(communityClass.get(i).contains(communityClass.get(j))){
					communityClass.remove(j);
					j --;
				}
			}
		}
		//get rid of indenpendent vertex
		for(String community : communityClass){
			String[] vertexArr = community.split("_");
			for(String vertex : vertexArr){
				if(vertexSet.contains(vertex)){
					vertexSet.remove(vertex);
				}
			}
		}
		String restVertex = "";
		for(String str : vertexSet){
			restVertex += str + "_";
		}
		if(restVertex.length() > 0 ){
			communityClass.add(restVertex.substring(0, restVertex.length() - 1));
		}
		return communityClass;
	}

	/**
	 * judge the matrix is a equivalence matrix
	 * @param matrix
     * @return
     */
	private boolean isEquivalenceMatrix(double[][] matrix){
		int size = matrix.length;
		double[][] fuzzyEquivalenceMatrix = new double[size][size];
		for (int i = 0 ; i < size; i ++){
			for(int j = 0; j < size ; j ++){
				if(i == j){
					//???
					if(matrix[i][j] != 1.0){
						return false;
					}
				}else if(matrix[i][j] != matrix[j][i]){
					//???
					return false;
				}
			}
		}
		fuzzyEquivalenceMatrix = getEquivalenceMatrix(matrix, matrix);
		for (int i = 0 ; i < size; i ++){
			for(int j = 0; j < size ; j ++){
				if(matrix[i][j] >= fuzzyEquivalenceMatrix[i][j]){
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * get similar of two community
	 * @param vertexInterfaceSet
	 * @param vertexInterfaceSet1
     * @return
     */
	private Double getSimilar(Set<VertexInterface> vertexInterfaceSet, Set<VertexInterface> vertexInterfaceSet1) {
		int size = vertexInterfaceSet.size();
		int size1 = vertexInterfaceSet1.size();
		double[][] matrix = new double[size][size1];
		List<VertexInterface> vertexInterfaceList = new ArrayList<VertexInterface>(vertexInterfaceSet);
		List<VertexInterface> vertexInterfaceList1 = new ArrayList<VertexInterface>(vertexInterfaceSet1);
		if(vertexInterfaceList.containsAll(vertexInterfaceList1) && vertexInterfaceList1.containsAll(vertexInterfaceList)){
			//is a same community
			for(int i = 0; i < size; i ++){
				for(int j = 0; j < size1; j ++){
					matrix[i][j] = 1.0;
				}
			}
		}else {//is not a same community use jackard
			matrix = getSimilarMatrix(vertexInterfaceList, vertexInterfaceList1);
		}
		double similar = 0.0;
		int sum = 0;
		for(int i = 0; i < size; i ++){
			for(int j = 0; j < size1; j ++){
				if(matrix[i][j] != 0.0 ){
					similar += matrix[i][j];
					sum ++;
				}
			}
		}
		if(sum == 0){
			return 0.0;
		}
		return similar / sum;
	}

	/**
	 * get simialr matrix of two community
	 * @param vertexInterfaceList
	 * @param vertexInterfaceList1
     * @return
     */
	private double[][] getSimilarMatrix(List<VertexInterface> vertexInterfaceList, List<VertexInterface> vertexInterfaceList1){
		int size = vertexInterfaceList.size();
		int size1 = vertexInterfaceList1.size();
		double[][] fuzzySimilarMatrix = new double[size][size1];
		for(int i = 0; i < size; i ++){
			for(int j = 0; j < size1; j ++){
				String name1 = vertexInterfaceList.get(i).getName();
				String name2 = vertexInterfaceList1.get(j).getName();
				if(name1.equals(name2)){
					//is a same vertex
					fuzzySimilarMatrix[i][j] = 1;
				}else {
					//is not a same vertex ,get common vertex and union vertex
					Set<VertexInterface> vertexInterfaceSet = new HashSet<VertexInterface>();
					Set<VertexInterface> vertexInterfaceSet1 = new HashSet<VertexInterface>();
					for(VertexInterface vertexInterface : vertexList){
						String name  = vertexInterface.getName();
						if(name.equals(name1)){
							List<Edge> edgeList = vertexInterface.getEdgeList();
							for(Edge edge : edgeList){
								vertexInterfaceSet.add(edge.getEndVertex());
							}
						}
						if(name.equals(name2)){
							List<Edge> edgeList = vertexInterface.getEdgeList();
							for(Edge edge : edgeList){
								vertexInterfaceSet1.add(edge.getEndVertex());
							}
						}
					}
					int commonVertex = 0;
					if(vertexInterfaceSet.size() == 0 || vertexInterfaceSet1.size() == 0){
						fuzzySimilarMatrix[i][j] = 0;
					}else {
						List<String> nameList = new ArrayList<String>();
						List<String> nameList1 = new ArrayList<String>();
						for(VertexInterface vertexInterface1 : vertexInterfaceSet){
							nameList.add(vertexInterface1.getName());
						}
						for(VertexInterface vertexInterface2 : vertexInterfaceSet1){
							nameList1.add(vertexInterface2.getName());
						}
						for(VertexInterface vertexInterface1 : vertexList){
							String name3 = vertexInterface1.getName();
							if(nameList.contains(name3) && nameList1.contains(name3)){
								commonVertex ++;
							}
						}
						int unionVertex = vertexInterfaceSet.size() + vertexInterfaceSet1.size() - commonVertex;
						double similar = commonVertex / (double) unionVertex;
						BigDecimal bigDecimal = new BigDecimal(similar);
						similar = bigDecimal.setScale(3, RoundingMode.UP).doubleValue();
						fuzzySimilarMatrix[i][j] = similar;
					}
				}
			}
		}
		return fuzzySimilarMatrix;
	}

	private double[][] getUnionMatrix(double[][] fuzzySimilarMatrix, double[][] fuzzyEquivalenceMatrix){
		int size = fuzzySimilarMatrix.length;
		double[][] finalMatrix = new double[size][size];
		for(int i = 0; i < size; i ++) {
			for(int j = 0; j < size; j ++){
				double a = fuzzySimilarMatrix[i][j];
				double b = fuzzyEquivalenceMatrix[i][j];
				finalMatrix[i][j] = a > b ? a : b;
			}
		}
		return finalMatrix;
	}

	/**
	 * get equivalence matrix of two community
	 * @param matrix1
     * @return
     */
	private double[][] getEquivalenceMatrix(double[][] matrix1, double[][] matrix2){
		int size = matrix1.length;
		double[][] fuzzyEquivalenceMatrix = new double[size][size];
		for(int i = 0; i < size; i++){
			double[] a = new double[size];
			for(int j = 0; j < size; j++){
				int temp = 0;
				for(int k = 0; k < size; k++){
					a[temp++] = Math.min(matrix1[i][k],matrix2[k][j]);
				}
				Arrays.sort(a);
				fuzzyEquivalenceMatrix[i][j] = a[a.length-1];
			}
		}
		return fuzzyEquivalenceMatrix;
	}

	private void combineFuzzyVertes() {
		List<VertexInterface> fuzzyVertexList = restIndependentVertexs;
		HashMap<Integer, String> vertexMap = new HashMap<Integer, String>(16);
		int size = fuzzyVertexList.size();
		int[][] matrix  = new int[size][size];
		double[][] fuzzySimilarMatrix  = new double[size][size];
		double[][] fuzzySimilarMatrix1  = new double[size][size];
		double[][] fuzzyEquivalenceMatrix = new double[size][size];
		System.out.println("???????????");
		int num = 1;
		for(VertexInterface vertexInterface : fuzzyVertexList){
			System.out.println("?????"+vertexInterface.getName() + " ");
			vertexMap.put(num, vertexInterface.getName());
			num ++;
		}
		System.out.println();
		for(int i = 0; i < size;i ++){
			for(int j = 0;j < size;j ++){
				if(isNeighbor(fuzzyVertexList.get(i),fuzzyVertexList.get(j))){
					matrix[i][j] = 1;
				}else {
					matrix[i][j] = 0;
				}
			}
		}
		System.out.println("?????????");
		for(int i = 0; i < matrix.length; i ++) {
			for(int j = 0; j < matrix.length; j ++){
				System.out.print(matrix[i][j] + " ");
				fuzzySimilarMatrix[i][j] = consineSimilar.cosine(matrix, i ,j);
			}
			System.out.println();
		}
		System.out.println();
		fuzzySimilarMatrix1 = fuzzySimilarMatrix;
		System.out.println("?????????");
		for(int i = 0; i < fuzzySimilarMatrix.length; i ++) {
			for(int j = 0; j < fuzzySimilarMatrix.length; j ++){
				System.out.printf("%1.3f",fuzzySimilarMatrix[i][j]);
				System.out.print("  ");
			}
			System.out.println();
		}
		System.out.println();
		//??????????????(????)
		int n = 1;
		do{
			fuzzyEquivalenceMatrix = getEquivalenceMatrix(fuzzySimilarMatrix, fuzzySimilarMatrix1);
			fuzzySimilarMatrix = fuzzyEquivalenceMatrix;
			n ++;
		}while (n <= size);
		System.out.println("?????????");
		for(int i = 0; i < fuzzyEquivalenceMatrix.length; i ++) {
			for(int j = 0; j < fuzzyEquivalenceMatrix.length; j ++){
				System.out.printf("%1.3f",fuzzySimilarMatrix[i][j]);
				System.out.print("  ");
			}
			System.out.println();
		}
		System.out.println();
		localMinCommunity = new HashMap<Set<String>, Set<VertexInterface>>(16);
		Map<Integer, List<String>> vertexClass = communityClassifiy(fuzzyEquivalenceMatrix);
		for(Integer integer : vertexClass.keySet()){
			List<String> stringList = vertexClass.get(integer);
			System.out.println("???????" + stringList);
			Set<String> keyName = new HashSet<>();
			Set<VertexInterface> vertexInterfaceSet = new HashSet<VertexInterface>();
			for(String str : stringList){
				List<String> vertexInterfaceList1 = new ArrayList<String>();
				String[] arr = str.split("_");
				for(String s : arr){
					String res = vertexMap.get(Integer.valueOf(s));
					if(!vertexInterfaceList1.contains(res)){
						vertexInterfaceList1.add(res);
					}
				}
				for(String vertexName : vertexInterfaceList1){
					keyName.add(vertexName);
					System.out.print(vertexName+" ");
					for(VertexInterface vertexInterface : vertexList){
						if(vertexName.equals(vertexInterface.getName())){
							vertexInterfaceSet.add(vertexInterface);
						}
					}
				}
				System.out.println();
			}
			localMinCommunity.put(keyName, vertexInterfaceSet);
		}
	}

	/**
	 * merge fuzzy vertex by R function
     */
	private void mergeFuzzyVertexByRfunction() {
		System.out.println("The number of final community is " + localMinCommunity.size());
		Iterator<VertexInterface> iterator = restIndependentVertexs.iterator();
		while(iterator.hasNext()){
			VertexInterface vertexInterface = iterator.next();
			System.out.println("The vertex name is " + vertexInterface.getName());
			Set<VertexInterface> vertexInterfaceSet = new HashSet<VertexInterface>();
			vertexInterfaceSet.add(vertexInterface);
			Iterator<Set<String>> setIterator = localMinCommunity.keySet().iterator();
			double difference = 0;
			Set<String> keyName = new HashSet<String>();
			while(setIterator.hasNext()){
				Set<String> vertexSet = setIterator.next();
				Set<VertexInterface> community = localMinCommunity.get(vertexSet);
				Set<VertexInterface> vertexInterfaces = new HashSet<VertexInterface>();
				vertexInterfaces.addAll(community);
				System.out.println("The vertexs of community include: ");
				for(VertexInterface vertexInterface1 : community){
					System.out.print(vertexInterface1.getName() + " ");
				}
				System.out.println();
				System.out.println("添加前");
				double r1 = modularityR(vertexInterfaces);
				vertexInterfaces.addAll(vertexInterfaceSet);
				System.out.println("添加后");
				double r2 = modularityR(vertexInterfaces);
				double temp = r2 - r1;
				System.out.println("The difference of R: "+temp);
				if(temp > 0){
					if(temp > difference){
						difference = temp;
						keyName = vertexSet;
					}
				}
			}
			if(keyName.size() != 0){
				localMinCommunity.get(keyName).add(vertexInterface);
				iterator.remove();
			}
			System.out.println();
		}
	}


	private void removeRepeatVertics() {
		Iterator<Set<String>> it = localMinCommunity.keySet().iterator();
		List<Set<String>> allNeedRemove = new ArrayList<Set<String>>();
		while(it.hasNext()){
			Set<String> key = it.next();
			if(key.size() <= 2){
				allNeedRemove.add(key);
			}
		}
		for (Iterator iterator = allNeedRemove.iterator(); iterator.hasNext();) {
			Set<String> set = (Set<String>) iterator.next();
			restIndependentVertexs.addAll(localMinCommunity.get(set));
			localMinCommunity.remove(set);
		}
	}

	private void reCreatlocalMinCoummunity(List<VertexInterface> restIndependVertexs) {
		Set<VertexInterface> needremove = new HashSet<VertexInterface>();
		for(VertexInterface vertexInterface : restIndependVertexs) {
			Set<VertexInterface> neighbors = getNeighbors(vertexInterface);
			Set<String> keys = new HashSet<String>();
			HashSet<VertexInterface> minCommunity = new HashSet<VertexInterface>();
			double min = 0;
			for (VertexInterface vertexInterface2 : neighbors) {
				if(!restIndependVertexs.contains(vertexInterface)){
					continue;
				}
				double d2 = vertexInterface2.getDensity();
				if(d2 > min){
					min = d2;
					minCommunity.clear();
					minCommunity.add(vertexInterface2);
				}else if(d2 == min){
					minCommunity.add(vertexInterface2);
				}
			}
			Iterator<VertexInterface> it = minCommunity.iterator();
			while(it.hasNext()){
				VertexInterface ver = it.next();
				needremove.add(ver);
				keys.add(ver.getName());
			}
			keys.add(vertexInterface.getName());
			minCommunity.add(vertexInterface);
			localMinCommunity.put(keys, minCommunity);
		}
		restIndependentVertexs.removeAll(needremove);
	}

	private void mergeCommunityInit() {
		double q1 = figureQ(localMinCommunity, false);
		Iterator<Set<String>> setIterator = localMinCommunity.keySet().iterator();
		while(setIterator.hasNext()){
			Set<String> vertexSet = setIterator.next();
			Set<VertexInterface> unitCommunity = localMinCommunity.get(vertexSet);
			double r1 = modularityR(unitCommunity);
			Set<Set<String>> nearCommunities = new HashSet<Set<String>>();
			for(VertexInterface vertexInterface : unitCommunity) {
				nearCommunities.addAll(getNearCommunityByVertex(vertexInterface));
			}
			Iterator<Set<String>> setIterator1 = nearCommunities.iterator();
			double r3 = 0;
			Set<String> vertexSet1 = null;
			double maxdR = 0;
			while(setIterator1.hasNext()){
				Set<String> vertexSet2 = setIterator1.next();
				if(vertexSet == vertexSet2) {
					continue;
				}
				if(vertexSet2.containsAll(vertexSet)){
					localMinCommunity.remove(vertexSet);
					mergeCommunityInit();
					return;
				}else if(vertexSet.containsAll(vertexSet2)){
					localMinCommunity.remove(vertexSet2);
					mergeCommunityInit();
					return;
				}
				Set<VertexInterface> nearCommunity = localMinCommunity.get(vertexSet2);
				double r2 = modularityR(nearCommunity);
				Set<VertexInterface> newCommunity = new HashSet<VertexInterface>();
				newCommunity.addAll(unitCommunity);
				newCommunity.addAll(nearCommunity);
				double tR = modularityR(newCommunity);
				double dr = tR - r2;
				if(tR > r2 && dr > maxdR){
					maxdR = dr;
					r3 = tR;
					vertexSet1 = vertexSet2;
				}
			}
			if(r3 != 0){
				Map<Set<String>,Set<VertexInterface>> obj = new LinkedHashMap<Set<String>, Set<VertexInterface>>(localMinCommunity);
				Set<VertexInterface> newLocalCommunity = new HashSet<VertexInterface>();
				newLocalCommunity.addAll(unitCommunity);
				newLocalCommunity.addAll(obj.get(vertexSet1));
				Set<String> stringSet = new HashSet<String>();
				obj.remove(vertexSet);
				obj.remove(vertexSet1);
				stringSet.addAll(vertexSet1);
				stringSet.addAll(vertexSet);
				obj.put(stringSet, newLocalCommunity);
				double q2 = figureQ(obj, false);
				double averageDensity = totalDensity / getNumberOfVertices();
				if((averageDensity > 0.11) || q2 > q1){
					localMinCommunity = obj;
					mergeCommunityInit();
					return;
				}
			}
		}
		return;
	}

	private void forceCombineSingleVertes(){
		List<VertexInterface> needRemoveIndependVertex = new ArrayList<VertexInterface>();
    	Collections.sort(restIndependentVertexs, new Comparator<VertexInterface>(){
    		@Override
    		public int compare(VertexInterface o1, VertexInterface o2) {
    			double q1 = o1.getDensity();
    			double q2 = o2.getDensity();
    			if(q1 == q2){
            		return 0;
            	}else if(q1 > q2){
            		return -1;
            	}else{
            		return 1;
            	}
    		}
    	});
    	for (VertexInterface vertexInterface : restIndependentVertexs) {
    		Set<Set<String>> nearbyCommunity = getNearCommunityByVertex(vertexInterface);
    		if(nearbyCommunity.size() == 0){
    			continue;
    		}
    		Set<VertexInterface> neighbors = getNeighbors(vertexInterface);
    		int total = 0;
    		int maxEdges = 0;
    		Set<String> maxKeyName = null;
    		Boolean isRepeat = false;
    		for (Set<String> keyName : nearbyCommunity) {
    			Integer numEd = 0;
    			for(VertexInterface v : neighbors){
    				if(keyName.contains(v.getName())){
    					numEd++;
    				}
    			}
    			total += numEd;
    			if(numEd > maxEdges){
    				maxKeyName = keyName;
    				maxEdges = numEd;
    				isRepeat = false;
    			}else if(numEd == maxEdges){
    				isRepeat = true;
    			}
    		}
    		if(maxKeyName != null && isRepeat == false){
    			needRemoveIndependVertex.add(vertexInterface);
    			Set<String> newKey = new HashSet<String>(maxKeyName);
    			newKey.add(vertexInterface.getName());
    			Set<VertexInterface> newValue = new HashSet<VertexInterface>(localMinCommunity.get(maxKeyName));
    			newValue.add(vertexInterface);
    			localMinCommunity.put(newKey, newValue);
    			localMinCommunity.remove(maxKeyName);
    		}
		}
    	restIndependentVertexs.removeAll(needRemoveIndependVertex);
	}

	@Override
	public List<VertexInterface> getBoundaryVertices() throws Exception {
		return restIndependentVertexs;
	}

	@Override
	public int[][] initMatrix() throws Exception {
		List<VertexInterface> fuzzyVertex = new ArrayList<>(vertexList);
		Collections.sort(fuzzyVertex, new Comparator<VertexInterface>(){
			@Override
			public int compare(VertexInterface o1, VertexInterface o2) {
				String q1 = o1.getName();
				String q2 = o2.getName();
				if(q1.equals(q2)){
					return 0;
				}else if(Integer.parseInt(q1) > Integer.parseInt(q2)){
					return 1;
				}else{
					return -1;
				}
			}
		});
		int size = fuzzyVertex.size();
		int[][] matrix = new int[size][size];
		for(int i = 0; i < size;i ++){
			for(int j = 0;j < size;j ++){
				if(isNeighbor(fuzzyVertex.get(i),fuzzyVertex.get(j))){
					matrix[i][j] = 1;
				}else {
					matrix[i][j] = 0;
				}
			}
		}
		return matrix;
	}

	@Override
	public double getPrecision() {
		return 0;
	}

	@Override
	public double getRecall() {
		return 0;
	}

	@Override
	public double getF1() {
		return 0;
	}
}
